Public key cryptography utilizes a public key and a private key that are mathematically related. The relationship is such that the public key can readily be computed from the private key but computation of the private key from the public key is considered infeasible. The private key is thus maintained secret. The keys are used in a variety of well known protocols to secure or sign messages. To secure a message, the public key of the recipient is used by the sender to encrypt the message and the recipient uses his private key to decrypt the message. To sign a message, the author uses her private key to generate a signature which can be verified by use of the public key by any recipient. In each case, the public key has to be obtained from a trusted party, such as a trusted authority (“TA”).
In identity-based public key cryptography, an entity's public key is its identity, such as an e-mail address, or a derivation thereof. An identity-based encryption (“IBE”) system has numerous advantages, most notably:                1. No need for a sender to obtain a public key before encrypting a message;        2. Encryption can be done by the sender before the recipient possesses a private key;        3. Identities can be chosen by the sender, not just the recipient;        4. Existing identities and addresses can be made into public keys; and        5. Public keys can be humanly memorizable.        
Many identity-based encryption schemes have been proposed. In one simple scheme, each user is responsible for generating its own private/public key pair. The user does not disclose its private key to anyone, including the TA. Each user may simply adopt its public key as its identity, for example, using it as an e-mail or website address. The user, however, would have to be content with whatever public key that may be generated and use it (or a representation thereof) as its identity, such as an e-mail address or website address. There are other IBE schemes proposed as well, but none has been deemed practical.
It is an object of the present invention to mitigate or obviate at least one of the above mentioned disadvantages.